РНК можно рассматривать как длинную цепочку, составленную из нуклеотидов. В этой задаче нуклеотидом будем называть один из символов 'U', 'C', 'A', 'G'. Три подряд идущих нуклеотида образуют кодон (порядок нуклеотидов в кодоне важен). Каждому кодону соответствует некоторая аминокислота, при этом нескольким различным кодонам может соответствовать одна и та же аминокислота:
Соответствие кодонов аминокислотам Выберем первый нуклеотид в центре, далее будем переходить на следующее кольцо по соответствующему нуклеотиду, соседнему со стороной фигуры.
Например, «AUG» — это кодон, который соответствует аминокислоте 'M'.
Обратите внимание, что старт кодон выглядит как «AUG», а стоп кодон — это один из вариантов: «UAA», «UAG», «UGA».
Будем говорить, что белок — это последовательность аминокислот, которая начинается с аминокислоты 'M' и заканчивается одной из аминокислот, являющихся стоп-кодоном (такие аминокислоты обозначены в таблице кружком). Стоп-кодон не может встречаться в середине белка. Аминокислота 'M', напротив, может встречаться несколько раз.
Биолог исследует белок длины $$$n$$$. При синтезе РНК произошла ошибка: в неё было вставлено ещё $$$k$$$ нуклеотидов в произвольные места. В результате получилась последовательность из $$$3n + k$$$ нуклеотидов, и биолог хочет восстановить какой-нибудь белок длины $$$n$$$.
В первой строке записано одно целое число $$$t$$$ — количество наборов входных данных. В этой версии задачи во всех тестах $$$t=1$$$.
Во $$$2\cdot (t + 1)$$$-й строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^5$$$).
В $$$2\cdot (t + 1) + 1$$$-й строке записана строка длины $$$3n + k$$$, которая является последовательностью нуклеотидов. Гарантируется, что строка содержит только символы 'U', 'C', 'A', 'G'.
Выведите $$$t$$$ строк, в каждой из них $$$k$$$ различных целых чисел — номера удаляемых нуклеотидов в тесте $$$t$$$. Номера можно выводить в любом порядке.
В этой версии задачи $$$40$$$ тестов помимо тестового примера из условия, каждый оценивается в $$$1$$$ балл. Тестовый пример не оценивается.
Длина восстановленного белка $$$len$$$ определяется следующим образом.
Рассмотрим строку, полученную после удаления некоторых нуклеотидов, и разобьём её на кодоны. Затем найдём первое вхождение старт-кодона и первое вхождение стоп-кодона, расположенное после него. Тогда длиной белка будем считать количество аминокислот от 'M' до этого стоп-кодона включительно.
Количество баллов за тест определяется по формуле $$$$$$score = \frac{len}{n}.$$$$$$
Обратите внимание, что если у вас выполнится одно из трёх условий:
- Нет ни одного старт кодона
- Нет ни одного стоп кодона
- Все старт кодоны находятся после всех стоп кодонов
| Подзадача | Баллы | Доп. ограничения |
| 0 | 0 | тесты из условия |
| 1 | 8 | $$$2 \le n \le 6$$$, $$$1 \le k \le 6$$$ |
| 2 | 8 | $$$k = 1$$$ |
| 3 | 8 | $$$k = 2$$$ |
| 4 | 8 | $$$k = 3$$$ |
| 5 | 8 | Вставка происходит только между соседними кодонами |
12 1AUUGUGA
3
Для удобства обозначим стоп кодон как 'e'.
В первом примере после удаления нуклеотидов под номером $$$3$$$ получим последовательность нуклеотидов AUGUGA, разобьём её на кодоны AUG, UGA — это соответствует белку Me. Его длина равна 2.